Search Results

Many important graph classes are characterized by means of layouts (a vertex ordering) excluding some patterns. For example, a graph G = (V,E) is a proper interval graph if and only if G has a layout 𝐋 such that for every triple of vertices such that x≺_𝐋 y≺_𝐋 z, if xz ∈ E, then xy ∈ E and yz ∈ E. Such a triple x, y, z is called an indifference triple. In this paper, we investigate the concept of excluding a set of patterns in tree-layouts rather than layouts. A tree-layout 𝐓_G = (T,r,ρ_G) of a graph G = (V,E) is a tree T rooted at some node r and equipped with a one-to-one mapping ρ_G between V and the nodes of T such that for every edge xy ∈ E, either x is an ancestor of y, denoted x≺_{𝐓_G} y, or y is an ancestor of x. Excluding patterns in a tree-layout is now defined using the ancestor relation. This leads to an unexplored territory of graph classes. In this paper, we initiate the study of such graph classes with the class of proper chordal graphs defined by excluding indifference triples in tree-layouts. Our results combine characterization, compact and canonical representation as well as polynomial time algorithms for the recognition and the graph isomorphism of proper chordal graphs. For this, one of the key ingredients is the introduction of the concept of FPQ-hierarchy generalizing the celebrated PQ-tree data-structure.